package codeRandomThoughts.Test105从前序与中序遍历序列构造二叉树;

import codeRandomThoughts.utils.TreeNode;

import java.util.Arrays;

//二刷
public class Solution2 {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        //递归终止条件
        //数组为空代表遍历到了空结点
        if (preorder.length == 0) {
            return null;
        }

        //前序遍历数组的第一个元素是根节点
        int rootVal = preorder[0];
        TreeNode root = new TreeNode(rootVal);

        //找根节点在中序遍历数组中的位置
        int rootIndex = 0;
        for (int i = 0; i < inorder.length; i++) {
            if (inorder[i] == rootVal) {
                rootIndex = i;
                break;
            }
        }

        //把原来的中序序列按左右子树进行划分
        int[] inorderLeft = Arrays.copyOfRange(inorder, 0, rootIndex);
        int[] inorderRight = Arrays.copyOfRange(inorder, rootIndex + 1, inorder.length);

        //把原来的前序序列按左右子树进行划分
        int[] preorderLeft = Arrays.copyOfRange(preorder, 1, inorderLeft.length + 1);
        int[] preorderRight = Arrays.copyOfRange(preorder, inorderLeft.length + 1, preorder.length);

        root.left = buildTree(preorderLeft, inorderLeft);
        root.right = buildTree(preorderRight, inorderRight);
        return root;

    }

}
